package cmlabs.moduloariphmetics;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public class Polynomial {
    private BitSet coefs;
    private GF2Field parameters;

    public Polynomial(int[] bitsAsCoefs, GF2Field parent) {
        this.parameters = parent;
        this.coefs = new BitSet(parent.getSize() * (parent.getSize() + 1));
        for (int set : bitsAsCoefs) {
            this.coefs.set(set);
        }

    }

    public Polynomial(Integer[] bitsAsCoefs, GF2Field parent) {
        this.parameters = parent;
        this.coefs = new BitSet(parent.getSize() * (parent.getSize() + 1));
        for (int set : bitsAsCoefs) {
            this.coefs.set(set);
        }
    }

    public Polynomial(Polynomial another) {
        this.parameters = another.parameters;
        this.coefs = (BitSet) another.coefs.clone();
    }

    public Polynomial(String bits, GF2Field parent) {
        this.parameters = parent;
        this.coefs = new BitSet(parent.getSize() * (parent.getSize() + 1));
        for (int i = 0; i < bits.length(); ++i) {
            if (bits.charAt(i) == '1') {
                this.coefs.set(bits.length() - 1 - i);
            }
        }
    }

    @Override
    public int hashCode() {
        int result = 0;
        result += this.coefs.hashCode();
        result += this.parameters.getGenerator().coefs.hashCode() + this.parameters.getSize();
        return result;
    }

    @Override
    public String toString() {
        int last = this.coefs.nextSetBit(0);
        if (last == -1) {
            return "0";
        }
        while (this.coefs.nextSetBit(last + 1) != -1) {
            last = this.coefs.nextSetBit(last + 1);
        }
        StringBuilder ret = new StringBuilder();
        for (int i = last; i >= 0; --i) {
            ret.append(this.coefs.get(i) ? '1' : '0');
        }
        return ret.toString();
    }

    private void reduce() {
        int last = this.coefs.nextSetBit(0);
        while (this.coefs.nextSetBit(last + 1) != -1) {
            last = this.coefs.nextSetBit(last + 1);
        }
        while (last >= this.parameters.getSize()) {
            mod(last - this.parameters.getSize(), this.parameters.getGenerator());
            last = this.coefs.nextSetBit(0);
            while (this.coefs.nextSetBit(last + 1) != -1) {
                last = this.coefs.nextSetBit(last + 1);
            }
        }
    }

    // counts our polynomial mod generator of the field
    private void mod(int bit, Polynomial modulus) {
        BigInteger toReduce = new BigInteger(this.toString(), 2);
        BigInteger dividor = new BigInteger(modulus.toString(), 2);
        dividor = dividor.shiftLeft(bit);
        toReduce = toReduce.xor(dividor);
        this.coefs.xor(this.coefs);
        String bits = toReduce.toString(2);
        for (int i = 0; i < bits.length(); ++i) {
            if (bits.charAt(i) == '1') {
                this.coefs.set(bits.length() - 1 - i);
            }
        }
    }

    //returns an array, result[0] - a / b, result[1] = a % b
    public Polynomial[] divide(Polynomial another) {
        if (another.coefs.nextSetBit(0) == -1) {
            throw new IllegalArgumentException("Division by zero");
        }
        List<Integer> divideBits = new ArrayList<Integer>();
        Polynomial[] result = new Polynomial[2];
        int last = this.coefs.nextSetBit(0);
        result[1] = new Polynomial(this);
        int limit = another.coefs.nextSetBit(0);
        while (another.coefs.nextSetBit(limit + 1) != -1) {
            limit = another.coefs.nextSetBit(limit + 1);
        }
        while (result[1].coefs.nextSetBit(last + 1) != -1) {
            last = result[1].coefs.nextSetBit(last + 1);
        }
        while (last >= limit) {
            divideBits.add(last - limit);
            result[1].mod(last - limit, another);
            last = result[1].coefs.nextSetBit(0);
            while (result[1].coefs.nextSetBit(last + 1) != -1) {
                last = result[1].coefs.nextSetBit(last + 1);
            }
        }
        Integer[] bits = new Integer[divideBits.size()];
        bits = divideBits.toArray(bits);
        result[0] = new Polynomial(bits, this.parameters);
        return result;
    }

    public Polynomial add(Polynomial another) {
        Polynomial result = new Polynomial(this);
        result.coefs.xor(another.coefs);
        return result;
    }

    public Polynomial subtract(Polynomial another) {
        Polynomial result = new Polynomial(this);
        result.coefs.xor(another.coefs);
        return result;
    }

    public Polynomial multiply(Polynomial another) {
        BigInteger temporary = new BigInteger(this.toString(), 2);
        BigInteger result = BigInteger.ZERO;
        List<Integer> bits = new ArrayList<Integer>();
        int last = another.coefs.nextSetBit(0);
        if (last != -1) {
            bits.add(last);
        }
        while (another.coefs.nextSetBit(last + 1) != -1) {
            last = another.coefs.nextSetBit(last + 1);
            bits.add(last);
        }
        for (Integer set : bits) {
            result = result.xor(temporary.shiftLeft(set));
        }
        Polynomial ret = new Polynomial(result.toString(2), this.parameters);
        ret.reduce();
        return ret;
    }
}
